/****************************************************
  @title: 数据结构实验
  @name: <实验9-1a> 顺序查找和折半查找a
  @object:
      [实验目的]
          实现顺序查找和折半查找，
          对两种查找方法作比较
      [实验提示]
          1. 编写顺序查找和折半查找算法
          2. 修改算法把查找过程中所作比较及其结果
             打印出来，观察并对比查找过程
          3. 分析并计算两种算法的平均查找长度
  @include:
  @usage:
      请查看"TO-DO列表",根据要求完成代码
  @copyright: BTC 2004, Zhuang Bo
  @author: Zhuang Bo
  @date: 2004
  @description:
*****************************************************/

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

//顺序查找
int SqSearch(ElemType a[],int n,ElemType x);
int SqSearch2(ElemType a[],int n,ElemType x); //打印查找过程 
//折半查找
int BinSearch(ElemType a[],int n,ElemType x);
int BinSearch2(ElemType a[],int n,ElemType x); //打印查找过程
//打印数组数据
void PrintArray(ElemType a[],int n);

int main()
{
	int i,x;
	//测试数据
	const int N = 9;
	ElemType a1[N+1]={0,34,23,12,56,90,78,89,45,67};
	ElemType a2[N+1]={0,12,23,34,45,56,67,78,89,90};

	//顺序查找
	printf("\n顺序查找\n");
	printf("a1[]="); 
	PrintArray(a1,N);
	
	printf("\n输入要查找的数据: ");
	scanf("%d",&x);
	
	if((i=SqSearch(a1,N,x))>0) //找到 
		printf("\n找到 x==a1[%d]\n",i);
	else //未找到 
		printf("\n找不到 %d \n",x);
	
	printf("\n查找过程:");
	SqSearch2(a1,N,x);
	printf("\n完成\n");

	//折半查找
	printf("\n折半查找\n");
	printf("a2[]=");
	PrintArray(a2,N);
	
	printf("\n输入要查找的数据: ");
	scanf("%d",&x);
	
	if((i=BinSearch(a2,N,x))>0) //找到 
		printf("\n找到 x==a2[%d]\n",i);
	else //未找到
		printf("\n找不到 %d \n",x);
	
	printf("\n查找过程:");
	BinSearch2(a2,N,x);
	printf("\n完成\n");

	system("pause");
	return 0;
}

//在数组a[1..n]中顺序查找x
//  找到时返回元素下标，否则返回0 
int SqSearch(ElemType a[],int n,ElemType x)
{
    //-------------------------------------
    // TODO (#1#): 顺序查找算法
    
    //-------------------------------------
	return 0; //找不到 
}

int SqSearch2(ElemType a[],int n,ElemType x)
{
    //-------------------------------------
    // TODO (#1#): 顺序查找算法，打印每次比较结果 
    
    //-------------------------------------
	return 0;
}

//在数组a[1..n]中折半查找x
//  找到时返回元素下标，否则返回0 
//前提：a[1..n]是非递减有序的 
int BinSearch(ElemType a[],int n,ElemType x)
{
    //-------------------------------------
    // TODO (#1#): 折半查找算法
    
    //-------------------------------------
	return 0; //找不到 
}

int BinSearch2(ElemType a[],int n,ElemType x)
{
    //-------------------------------------
    // TODO (#1#): 折半查找算法，打印每次比较结果
    
    //-------------------------------------
	return 0;
}

//打印数组数据a[1..n]
void PrintArray(int a[],int n)
{
	int i;
	printf("{ ");
	for(i=1; i<=n; i++)
		printf("%d ",a[i]);
	printf("}\n");
}

